
public class Grafo<E> implements InterfazGrafo<E>{
    private final int LIMITE = 10;
    private final int INFINITO = 999999;
    private Nodo nodos[];
    private int arcos[][];
    private int cantidadNodos;
    private int cantidadArbol;
    private Peso ruta[];
    private int nodoActual;
    private int costo;

    public Grafo() {
        
        nodos = new Nodo[LIMITE];
        arcos = new int[LIMITE][LIMITE];
        cantidadNodos = 0;
        cantidadArbol = 0;
        for(int i = 0; i < LIMITE; i++)
            for(int j = 0; j < LIMITE; j++)
                arcos[i][j] = INFINITO;
        ruta = new Peso[LIMITE];
   }

    public void nuevoNodo(E texto) {
        nodos[cantidadNodos++] = new Nodo(texto);
    }

    public void nuevoArco(int inicio, int fin, int costo) {
        arcos[inicio][fin] = costo;
    }

    public void ruta(int ini) {
        int inicio = ini ;
        nodos[inicio].enArbol = true;
        cantidadArbol = 1;

        for(int i=0; i<cantidadNodos; i++) {
            int costoTemp = arcos[inicio][i];
            ruta[i] = new Peso(inicio, costoTemp);
            
        }

        while(cantidadArbol < cantidadNodos) {
            int indiceMinimo = rutaMenor();
            int minimo = ruta[indiceMinimo].costo;

            if(minimo == INFINITO) {
                System.out.println("Existen nodos infinitos");
                break;
            }
            else {
                nodoActual = indiceMinimo;
                costo = ruta[indiceMinimo].costo;
                
            }

            nodos[nodoActual].enArbol = true;
            cantidadArbol++;
            ajustarRuta();
      }
    }

    public int rutaMenor() {
        int minimo = INFINITO;
        int indiceMinimo = 0;
        for(int i = 1; i < cantidadNodos; i++) {
            if(!nodos[i].enArbol && ruta[i].costo < minimo) {
                minimo = ruta[i].costo;
                indiceMinimo = i;
            }
        }

        return indiceMinimo;
    }

    public void ajustarRuta() {
        int columna = 1;
        while(columna < cantidadNodos) {
            if(nodos[columna].enArbol) {
                columna++;
                continue;
            }

            int actualArco = arcos[nodoActual][columna];
            int inicioArco = costo + actualArco;
            int costoruta = ruta[columna].costo;

            if(inicioArco < costoruta) {
                ruta[columna].padre = nodoActual;
                ruta[columna].costo = inicioArco;
            }

            columna++;
        }
    }

    public String darRutas() {
    	String mensaje = "";
        for(int i=0; i < cantidadNodos; i++) {
            mensaje += (nodos[i].texto + " = ");
            if(ruta[i].costo == INFINITO){
                mensaje += ("Infinito");}
            else{
                mensaje+=(ruta[i].costo);}
            
            E padre = (E) nodos[ruta[i].padre].texto;
            mensaje += (" desde " + padre.toString() + "\n");
        }
        return mensaje;
    }
    
    
}
